package BFS多源最短路问题;

import java.util.LinkedList;
import java.util.Queue;

/**
 * https://leetcode.cn/problems/as-far-from-land-as-possible/description/
 * 地图分析: 找一个最远的距离
 */
public class likou1162 {

    // bfs 用标记数组和sz.
    // 来一次多源bfs即可
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m, n;
    boolean[][] vis;
    public int maxDistance(int[][] grid) {

        m = grid.length;
        n = grid[0].length;
        // vis = new boolean[m][n];
        int[][] dist = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        //  先添加所有的0, 海洋. 添加海洋会错误.添加海洋会错误.添加海洋会错误.
        // 1. 先添加所有的1 陆地
        // 1. 先添加所有的1 陆地
        // 1. 先添加所有的1 陆地
        // 因为找的是最大值, 所以得添加陆地, 要是最小值的话就得添加海洋
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // if (grid[i][j] == 0) {
                if (grid[i][j] == 1) {
                    // vis[i][j] = true;
                    dist[i][j] = 0;
                    // 多源bfs, 加入所有的 0
                    queue.offer(new int[]{i, j});
                }else dist[i][j] = -1;
            }
        }

        // 2. bfs 主逻辑
        int step = 0, ret = 0;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            // 弹出下一层
            step++;
            while (sz-- != 0) {
                int[] tmp = queue.poll();
                int a = tmp[0], b = tmp[1];
                for (int i = 0; i < 4; i++) {
                    int x = a + dx[i], y = b + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {
                        dist[x][y] = step;
                        queue.offer(new int[]{x, y});
//                        if(grid[x][y] == 1) {
//                            ret = Math.max(ret, step);
//                            dist[x][y] = ret;
//                        }else {
//                            queue.offer(new int[]{x, y});
//                            dist[x][y] = 0;
//                        }
//                        vis[x][y] = true; // 标记这个位置添加过
                        dist[x][y] = step; // 标记这个位置遍历过. 没遍历过的都是 -1
                        queue.offer(new int[]{x, y}); // 添加到队列
                    }
                }
            }
        }
        // 3. 遍历原数组, 提取结果
        ret = -1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ret = Math.max(ret, dist[i][j]);
            }
        }
        return ret;
    }

}
